Leetcode刷题记录(Java)

Problem 47 Permutations II

在给定输入包含重复字符的情况下,求不重复的全排列

主要思路:
由于有重复元素,所以必须对元素进行排序,然后判断当前元素是否被使用过,如果被使用过则跳过.之后则开始元素交换,和所有采用回溯法解答的问题类似,要注意在退出递归时恢复现场.

代码实现:

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if (nums==null||nums.length==0)
            return res;
        Arrays.sort(nums);
        helper(res,nums,0);
        return res;
    }
    public void helper(List<List<Integer>> res,int[] nums,int start){
        if (start==nums.length){
            List<Integer> list = new ArrayList<>();
            for (int num:nums){
                list.add(num);
            }
            res.add(list);
            return;
        }
        for (int i=start;i<nums.length;i++){
            System.out.println("start:"+start+",i:"+i);
            if (isUsed(nums,start,i))
                continue;
            swap(nums,start,i);
            helper(res, nums, start+1);
            swap(nums,start,i);
        }
    }
    public void swap(int[] nums,int i,int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public boolean isUsed(int[] nums,int i,int j){
        for (int x=i;x<j;x++){
            if (nums[x]==nums[j])
                return true;
        }
        return false;
    }
}

代码说明:
为对代码进行理解,我直接采用数组[1,1,2]作为例子进行说明.

这个题目中主要是对 start 和 i 进行理解,首先最初的 start 为 0,而 i 也被赋值为 start,所以最开始的 i=start=0,两者交换(虽然此时相当于无效果)之后进入第一层递归 start+1=1,i=start=1,两者交换之后进入第二层递归,start+1=2,i=start=2,两者交换之后进入第三层递归,由于此时 start 已经和 nums.length 相同,所以加入到结果 list 当中.
此时注意 i 已经不满足 i 小于 nums.length 的条件,所以第三层递归顺序执行结束,跳出回到第二层递归,此时 start=1,i=1,然后执行循环,i++=2,所以能看到 start=1,i=2 的输出.然后判断是否使用过当前需要交换的数,位置 1 和位置 2 分别是 1 和 2,它们不相同则未使用过,将两者交换,此时原来的 112 变成了 121.然后进入第三层递归,i=start=2,所以交换无效,进入第四层递归,此时 start==nums.length,所以将 121 加入到结果 list 中.
通过类似的操作,得到 211 加入结果 list,完成全排列的组合.

Problem 55 Jump Game

给定一个数组,数组中的每个值代表你能从地点出发向前跳跃的最远距离,你最开始处于数组第一个值的位置.结果需要判断从初始位置出发能否跳到终点.

主要思路:
这个题目采用贪心算法对数组进行遍历,每次循环就判断从出发点出发能够跳到的最远距离.

代码实现:

class Solution {
    public boolean canJump(int[] nums) {
        int max = 0;
        for(int i=0;i<nums.length;i++){
            if (i>max)
                return false;
            max = Math.max(nums[i]+i,max);
        }
        return true;
    }
}

代码说明:
以题目中给定的情况进行说明.
在[2,3,1,1,4]中,最开始 i=max=0,此时 max=nums[0]=2,代表从初始点出发可以到达 2.循环开始,i=1,首先 i 和 max 比较,由于 i 代表的是数组的下标,所以如果 i>max 代表,从初始位置出发最远无法到达当前下标,故返回 false.之后对 max 进行更新,采用的规则是当前下标加上数组中该位置的数值,因为这代表了它能跳的最远距离,将它和原本的 max 比较取最大.

Problem 56 Merge Intervals

合并有交集的数组

主要思路:
这题采用了扫描线算法,简单来说就是先对数组进行排序,将每个元素按照 start 从小到大进行排列,然后遍历二维数组,比较相邻两个数组的 end 的大小，返回较大的那个 end,这样就完成了相邻两个数组的合并.但如果新进来的数组的 start 比之前那个数组的 end,则代表两个数组没有交集.

代码实现:

class Solution {
    public int[][] merge(int[][] intervals) {
        if (intervals==null||intervals.length<=1)
            return intervals;
        Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
        int start = intervals[0][0];
        int end = intervals[0][1];
        int count = 0;
        int[][] res = new int[intervals.length][];
        for (int[] interval:intervals){
            if (interval[0]<=end){
                end = Math.max(end,interval[1]);
            }else {
                res[count++] = new int[]{start,end};
                start = interval[0];
                end = interval[1];
            }
        }
        res[count] = new int[]{start,end};
        int len = 0;
        for (int[] re : res) {
            if (re != null)
                len++;
        }
        int[][] res2 = new int[len][];
        System.arraycopy(res,0,res2,0,len);
        return res2;
    }
}

Problem 61 Rotate List

对链表进行反转

主要思路:
先将链表成环,然后根据 K 值大小进行移动 head,最后返回 head.next,并且将 head.next 置为 null.

代码实现:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if(head==null||head.next==null)
            return head;
        ListNode index = head;
        int len = 1;
        while(index.next != null){
            index = index.next;
            len++;
        }
        index.next = head;
        for(int i=1;i<len-k%len;i++){
            head = head.next;
        }
        ListNode res = head.next;
        head.next = null;
        return res;
    }
}

⭐Problem 62 Unique Paths

计算一个只能向下或者向右移动的机器人在一个 m*n 的矩阵中从起点(左上角)移动到终点(右下角)存在的可能情况数量

主要思路:
本题利用动态规划的思想来解,由题目条件所知,要达到当前格子,那么必然来源于它的上方或者左方,所以只需要将它们相加就是达到当前格子可能的格子数

代码实现:

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] res = new int[m][n];
        for(int i=0;i<m;i++){
            res[i][0] = 1;
        }
        for(int j=0;j<n;j++){
            res[0][j] = 1;
        }
        for(int i=1;i<m;i++)
            for(int j=1;j<n;j++)
                res[i][j] = res[i-1][j]+res[i][j-1];
        return res[m-1][n-1];
    }
}

代码说明:

从上面这张示意图中能够看到运行过程

Problem 63 Unique Paths II

该题和上题基本要求一致,只是图中有障碍时不能通过

主要思路:
大致思路和上一题一致,只在遇到障碍时将数组置 0 即可

代码实现:

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int length = obstacleGrid[0].length;
        int[] res = new int[length];
        res[0] = 1;
        for(int i=0;i<obstacleGrid.length;i++)
            for(int j=0;j<length;j++){
                if(obstacleGrid[i][j]==1)
                    res[j] = 0;
                else if(j>0)
                    res[j] = res[j] + res[j-1];
            }
        return res[length-1];
    }
}

代码说明:
以
0 0 0
0 1 0
0 0 0
为例,初始化时 res[0]=1,自此开始第一行的扫描,由于第一行都没有为 1 的障碍,则第一轮结束后,res[0]=1,res[1]=1,res[2]=1,然后进入第二行的扫描,obstacleGrid[1][0]!=1 且 j 不大于 0,所以该轮不执行任何操作.因为要达到第一列上所有元素都只能从它上方移动到该位置,所以它不需要对 res 增加,res[0]=1,但是当遭遇障碍 1 时,res 需要重置.比如 obstacleGrid[1][1]=1,此时是 j=1,即 res[1]=0,res[2]=res[2]+res[1]=1+0=1.最后进入第三行的扫描,res[0]=1,res[1]=res[1]+res[0]=0+1=1,res[2]=res[2]+res[1]=2(这里代表了两条路径的汇合)

Problem 80 Remove Duplicates from Sorted Array II

去除数组中重复的数字,最多保留两个相同的数字,比如[1,1,1,2,2,3,3,3,3,4]则返回长度 7,数组则呈现为[1,1,2,2,3,3,4]

主要思路:
使用 count 进行插入位的计数,当遍历到当前元素时和 count-2 位的元素比较,如果不相同则代表相同元素数量超过了 2,需要用当前元素对 count-2 位的元素进行替换

class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums.length<=2)
            return nums.length;
        int count = 2;
        for (int i=2;i<nums.length;i++){
            if (nums[i]!=nums[count-2]){
                nums[count++] = nums[i];
            }
        }
        return count;
    }
}

Problem 82 Remove Duplicates from Sorted List II

删除有序链表中包含重复元素的项目

主要思路:
一般含有对链表操作的题目都先创建一个 dummy 结点,最后返回 dummy.next,在本题中主要需要注意设置循环删除相同的元素.

代码实现:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head==null || head.next==null){
            return head;
        }
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode p = dummy;
        while (p.next!=null&&p.next.next!=null){
            if (p.next.val==p.next.next.val){
                int sameNum = p.next.val;
                while (p.next!=null&&p.next.val==sameNum){
                    p.next = p.next.next;
                }
            }else {
                p = p.next;
            }
        }
        return dummy.next;
    }
}

⭐Problem 91 Decode Ways

根据给定的数字找到所有可能的字母组合结果

主要思路:
该题使用动态规划解决

代码实现:

class Solution {
    public int numDecodings(String s) {
        if (s==null||s.length()==0)
            return 0;
        int len = s.length();
        int[] dp = new int[len+1];
        dp[0] = 1;
        dp[1] = s.charAt(0)!='0'?1:0;
        for (int i=2;i<=len;i++){
            int first = Integer.valueOf(s.substring(i-1,i));
            int second = Integer.valueOf(s.substring(i-2,i));
            if (first>=1&&first<=9)
                dp[i] += dp[i-1];
            if (second>=10&&second<=26)
                dp[i] += dp[i-2];
        }
        return dp[len];
    }
}

代码说明:
以”1231”作为例子讲解
i=2,first=2,second=12,dp[0]=1,dp[1]=1,dp[2]=1=>dp[2]=2
i=3,first=3,second=23,dp[3]=3
i=4,first=1,second=31,dp[3]=3

Problem 92 Reverse Linked List II

将给定(m,n)区间的链表反转

代码实现:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode pre = dummy;
        ListNode cur = dummy.next;
        for (int i=1;i<m;i++){
            cur = cur.next;
            pre = pre.next;
        }
        for (int i=0;i<n-m;i++){
            ListNode temp = cur.next;
            cur.next = temp.next;
            temp.next = pre.next;
            pre.next = temp;
        }
        return dummy.next;
    }
}

代码说明:
同样先是创建 dummy 指针当作头结点,然后创建 pre 和 cur,其中 pre 是留在(m,n)前的指针,然后在(m,n)内部利用 cur,temp 转换

Problem 95 Unique Binary Search Trees II

给定 n,构建所有二叉平衡树

主要思路:
利用深度优先遍历构建树

代码实现:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<TreeNode> generateTrees(int n) {
        if (n==0)
            return new ArrayList<>();
        return genTreeList(1,n);
    }
    public List<TreeNode> genTreeList(int start,int end){
        List<TreeNode> list = new ArrayList<>();
        if (start>end){
            list.add(null);
        }
        for (int idx = start;idx<=end;idx++){
            List<TreeNode> leftList = genTreeList(start,idx-1);
            List<TreeNode> rightList = genTreeList(idx+1,end);
            for (TreeNode left:leftList){
                for (TreeNode right:rightList){
                    TreeNode root = new TreeNode(idx);
                    root.left = left;
                    root.right = right;
                    list.add(root);
                }
            }
        }
        return list;
    }
}

代码说明:
将每一个数字作为 idx,从 1 到 n,左子树就是 start 到 idx-1 的部分,右子树是 idx+1 到 end 的部分,分别构造完左子树和右子树之后,创建 root 结点并为它分配左右子树,构建结束